import collections
from typing import List


class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n
        self._group_num = n

    def find(self, i: int) -> int:
        """查询i所在的连通分支:O(1)"""
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        """合并i和j所属的连通分支:O(1)"""
        i, j = self.find(i), self.find(j)
        if i != j:
            self._group_num -= 1
            if self._size[i] >= self._size[j]:
                self._array[j] = i
                self._size[i] += self._size[j]
            else:
                self._array[i] = j
                self._size[j] += self._size[i]
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)

    @property
    def group_num(self):
        """计算连通分支数量:O(1)"""
        return self._group_num

    @property
    def max_group_size(self):
        """计算最大连通分支包含的数量:O(N)"""
        import collections
        return max(collections.Counter(self._array).values())


class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        words = set()
        for word1, word2 in synonyms:
            words.add(word1)
            words.add(word2)
        words = list(words)
        index = {word: i for i, word in enumerate(words)}

        dsu = DSU(len(words))
        for word1, word2 in synonyms:
            dsu.union(index[word1], index[word2])

        groups = collections.defaultdict(set)
        for word in words:
            groups[dsu.find(index[word])].add(word)

        change = {}
        for words in groups.values():
            for word in words:
                change[word] = words

        text = text.split()

        def dfs(i):
            j = i
            while j < len(text) and text[j] not in change:
                j += 1

            if j == len(text):
                return [text[i:]]

            left = text[i:j]
            now_options = sorted(change[text[j]])
            right_options = dfs(j + 1)

            res = []
            for now_option in now_options:
                for right_option in right_options:
                    res.append(left + [now_option] + right_option)
            return res

        ans = dfs(0)

        return [" ".join(item) for item in ans]


if __name__ == "__main__":
    # ["I am cheerful today but was sad yesterday",
    # "I am cheerful today but was sorrow yesterday",
    # "I am happy today but was sad yesterday",
    # "I am happy today but was sorrow yesterday",
    # "I am joy today but was sad yesterday",
    # "I am joy today but was sorrow yesterday"]
    print(Solution().generateSentences(synonyms=[["happy", "joy"], ["sad", "sorrow"], ["joy", "cheerful"]],
                                       text="I am happy today but was sad yesterday"))
